package com.zc.datastructure.structure.graph;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.CollectionUtils;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author: zhuCan
 * @date: 2020/6/27 10:45
 * @description:
 */
@Slf4j
@Data
public class ImmutableGraph<T> implements Graph<T>{

  // 图中所有的顶点
  public Vertex<T>[] heads;

  // 记录顶点是否被访问过,用于做遍历的
  public Map<String, Boolean> visited;

  /**
   * 创建一个只带空顶点的图
   *
   * @param vertex
   */
  public void create(List<String> vertex) {
    this.heads = vertex.stream().map(Vertex<T>::new).toArray(Vertex[]::new);
    visited = new HashMap<>();
  }

  /**
   * 添加边
   *
   * @param edge
   */
  public void addEdge(Edge<T> edge) {
    String edgeV = edge.getPrefix();
    // 查找这个边是属于哪个顶点的
    for (Vertex<T> head : heads) {
      if (head.getVertexData().equals(edgeV)) {

        // 查找到对应的顶点后,向这个顶点的边链表中插入数据
        Edge<T> firstEdge = head.getFirstEdge();
        if (firstEdge == null) {
          head.setFirstEdge(edge);
        } else {
          firstEdge.addEdge(firstEdge, edge);
        }
      }
    }
  }

  /**
   * 获取 以start为起点 图中所有路线中的顶点
   * 深度优先遍历
   *
   * @return
   */
  public List<String> DFS(String start, List<String> vertex) {
    // 记录已访问的顶点
    visited.put(start, Boolean.TRUE);
    log.info("遍历到节点:{}", start);
    vertex.add(start);

    for (Vertex<T> head : heads) {
      if (head.getVertexData().equals(start)) {

        for (Edge<T> edge = head.getFirstEdge(); edge != null; edge = edge.getNextEdge()) {
          if (!Boolean.TRUE.equals(visited.get(edge.getSuffix()))) {
            // 递归遍历
            DFS(edge.getSuffix(), vertex);
          }
        }
      }

    }
    return vertex;
  }

  /**
   * 获取指定俩个顶点之间路线的数据
   *
   * @param Start
   * @param end
   * @param data
   * @return
   */
  public Set<T> DFS(String Start, String end, Set<T> data) {
    // 记录已访问的顶点
    visited.put(Start, Boolean.TRUE);
    log.info("遍历到节点:{}", Start);

    for (Vertex<T> head : heads) {
      if (head.getVertexData().equals(Start)) {

        for (Edge<T> edge = head.getFirstEdge(); edge != null; edge = edge.getNextEdge()) {
          if (!Boolean.TRUE.equals(visited.get(edge.getSuffix()))) {
            log.info("经过边{}",edge.getData());
            // 递归遍历
            // 找到终点就停止
            if (edge.getSuffix().equals(end)) {
              data.addAll(edge.getData());
              return data;
            }
            Set<T> dfs = DFS(edge.getSuffix(), end, data);
            if (!CollectionUtils.isEmpty(dfs)) {
              data.addAll(dfs);
              return data;
            }

            visited.remove(edge.getSuffix());
          }
        }
      }

    }
    return data;
  }

  public void reset(){
    visited.clear();
  }
}
